1. Field of the Invention
This invention relates to the field of electronic communications. In particular, the present invention concerns optimally decoding data encoded with a cyclic code in communications systems where a convolutional code is applied after the cyclic code during the encoding process.
2. Description of the Related Art
In the field of electronic communications, channel coding is used to ensure the accuracy of data transmitted from one point to another. Channel coding refers to a class of signal transformations designed to improve communications performance by enabling the transmitted signals to better withstand the effects of various communications channel impairments, such as noise, fading, and jamming.
One set of channel coding techniques is referred to as linear block codes, which transform a block of k message bits into a longer block of n codeword bits. Binary cyclic codes are an important subclass of linear block codes. The codes are easily implemented with feedback shift registers in integrated circuits, and the underlying algebraic structure of cyclic codes lends itself to efficient decoding methods. Cyclic Redundancy Checks (CRC) are cyclic codes which are commonly used in communications systems, including cellular applications.
Another set of channel coding techniques is referred to as convolutional codes, which are described by three integers, n, k, and K. The integer K is a parameter known as the constraint length; it represents the number of k-tuple stages in the encoding shift register. An important characteristic of convolutional codes, which is not shared by linear block codes, is that the encoder has memory: The n-tuple emitted by the convolutional encoding procedure is not only a function of an input k-tuple, but also of the previous K-1 input k-tuples. Data which has been convolutionally encoded is often decoded using Viterbi decoders, which generally output decoded data in time reversed order.
Convolutional and linear block coding techniques are often combined, for example in wireless cellular communications systems, resulting in signficantly improved overall performance. Typical communications systems encode data first with a cyclic code for error detection, and then with a convolution code for error correction. A conventional receiver for such a system first uses a Viterbi decoder to decode the convolutional code and correct as many errors as possible. Then, a different decoder is used to decode the cyclic code and determine whether all of the errors were corrected or not.
In Code-Division Multiple Access (CDMA), Time-Division Multiple Access and most other cellular communications systems, data is divided into a number of "frames" including frame quality indicator bits (sometimes called "CRC bits") generated using a CRC code. The conventional method of calculating CRC bits is using a circuit provided in TIA Standards Proposal #3384, "lersonal Station Base Station Compatibility Requirements for 1.8 to 2.0 GHz Code Division Multiple Access Personal Communications Systems," and several related TIA Standards. The conventional method requires that the input bits be in normal time order (first bit in first), which is disadvantageous for the following reasons.
In most applications, the CRC bits in a receiver are calculated after a Viterbi decoder. Optimal Viterbi decoding requires a full "traceback" to calculate the input bits, which results in the input bits to the CRC generator being available in time reversed order. If the conventional method of calculating the CRC bits is used, the input bits need to be buffered up and fed into the CRC generator after all of the input bits are generated. It would be preferable to calculate CRC bits from a frame of data that is available in time reversed order (i.e., last bit available first) since this would allow the quality of a frame to be checked simultaneously with the Viterbi decoding, without buffering any bits. This reduces the hardware and other device complexity in implementation.
Therefore, an object of this invention is to provide a circuit which can decode in time reversed order, without buffering any bits, data encoded with a cyclic code in systems where a convolution code is applied after the cyclic code during the encoding process.